package medium;

import com.sun.jmx.remote.internal.ArrayQueue;
import sun.misc.Queue;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashSet;
import java.util.Set;

/**
 * @author cmqzyd0700@163.com
 * @version 1.0
 * @since 2021/5/28 19:02
 */
public class No3_无重复字符的最长子串 {
    public static void main(String[] args) {
        Solution3 solution3 = new Solution3();
        int res = solution3.lengthOfLongestSubstring("aab");
        System.out.println(res);
    }
}

class Solution3 {
    public int lengthOfLongestSubstring(String s) {
        //双指针
        Set<Character> set = new HashSet<>();
        int left = 0;
        int count = 0;
        for (int right = 0; right < s.length(); right++) {
            //right:右指针
            char check = s.charAt(right);
            if (set.add(check)) {
                //可以加
                //随便写点什么,空着不好看
                right = right;
            } else {
                //不能加
                while (set.contains(check)) {
                    //掐头
                    set.remove(s.charAt(left));
                    left++;
                }
                //加尾
                set.add(check);
            } 
            //一劳永逸
            count = Math.max(count, set.size());
        }
        return count;
    }
}



    //public int lengthOfLongestSubstring(String s) {
    //    //双端队列+set
    //    Deque<Character> deque = new ArrayDeque<>();
    //    //以空间换时间
    //    Set<Character> set = new HashSet<>();
    //    int count = 0;
    //    //遍历
    //    for (char c : s.toCharArray()) {
    //        if (set.add(c)) {
    //            //set能加
    //            deque.add(c);
    //        } else {
    //            //deque移除
    //            //set移除
    //            removeDS(deque, set, c);
    //        } 
    //        //deque里面必然不会存在重复元素
    //        //一劳永逸
    //        count = Math.max(count, deque.size());
    //    }
    //    return count;
    //}
    //
    ////定义deque,set删除逻辑
    //public void removeDS(Deque<Character> deque, Set<Character> set,
    //                     char c) {
    //    if (deque.isEmpty()) {
    //        return;
    //    }
    //    //deque: a   c:s
    //    
    //    //deque : as   c:s
    //    while (deque.getFirst() != c) {
    //        //set联动
    //        if (set.contains(deque.getFirst())) {
    //            set.remove(deque.getFirst());
    //        }
    //        deque.removeFirst();
    //    }
    //
    //    //deque:s
    //    //if (deque.isEmpty()) {
    //    //    deque.add(c);
    //    //} else {
    //    //    deque.removeFirst();
    //    //    deque.add(c);
    //    //} 
    //    if (!deque.isEmpty()) {
    //        deque.removeFirst();
    //    }
    //    deque.add(c);
    //}



    //public int lengthOfLongestSubstring(String s) {
    //    //暴力法优化
    //    //s:"a"
    //    Set<Character> set = new HashSet<>();
    //    int count = 0;
    //    out:for (int i = 0; i < s.length(); i++) { //大循环
    //        //完全注意点
    //        set.clear();
    //        for (int j = i; j < s.length(); j++) {//小循环,加set
    //            //元素
    //            char check = s.charAt(j);//绿指针指向位置
    //            if (set.isEmpty() || !set.contains(check)) {
    //                set.add(check);
    //            } else { //有重复元素进来
    //                
    //                //到下一个i
    //                break;
    //            } 
    //            //先获取长度
    //            //考虑s:"a" 情况
    //            //一劳永逸,每次判断确保不出问题
    //            count = Math.max(count, set.size());
    //            //如果j所在位置为最后且set满足题意,直接全部跳过
    //            //大优化
    //            if (j == s.length() - 1) {
    //                break out;
    //            }
    //        }
    //    }
    //    return count;
    //}



    //public int lengthOfLongestSubstring(String s) {
    //    //暴力法 
    //    //abcabcbb
    //    int l = s.length(); //13
    //    Set<Character> set = new HashSet<>();
    //    int count = 0;
    //    //开始循环取数并判断
    //    for (int i = 0; i < l; i++) { //轮数
    //        next:for (int j = 0; j <= i; j++) {//取数
    //            String check = s.substring(j, l - i + j);
    //            //注意这段代码!!
    //            set.clear();
    //            for (char c : check.toCharArray()) {
    //                if (!set.add(c)) {
    //                    //说明子串有重复
    //                    continue next;
    //                }
    //            }
    //            //记录长度! 最大长度
    //            count = Math.max(count, check.length());
    //        }
    //    }
    //    return count;
    //}








